<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>最小乘积算法解析 | 蓝桥杯专题</title>
    <link href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css" rel="stylesheet">
    <link href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css" rel="stylesheet">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
            background-color: #f8fafc;
            color: #1a202c;
            line-height: 1.6;
        }
        .hero-gradient {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
        }
        .code-block {
            background-color: #2d3748;
            border-left: 4px solid #667eea;
        }
        .card-hover {
            transition: all 0.3s ease;
        }
        .card-hover:hover {
            transform: translateY(-4px);
            box-shadow: 0 20px 25px -5px rgba(0, 0, 0, 0.1), 0 10px 10px -5px rgba(0, 0, 0, 0.04);
        }
        .drop-cap::first-letter {
            float: left;
            font-size: 4em;
            line-height: 0.8;
            margin: 0.1em 0.1em 0.1em 0;
            color: #667eea;
            font-weight: 700;
        }
    </style>
</head>
<body class="antialiased">
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20 px-4 sm:px-6 lg:px-8">
        <div class="max-w-4xl mx-auto text-center">
            <h1 class="text-4xl md:text-5xl font-bold mb-6 font-serif">最小乘积算法解析</h1>
            <p class="text-xl md:text-2xl opacity-90 mb-8 font-serif">蓝桥杯经典算法题解 - 贪心策略的优雅应用</p>
            <div class="flex justify-center space-x-4">
                <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm font-medium">贪心算法</span>
                <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm font-medium">数组排序</span>
                <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm font-medium">时间复杂度</span>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <div class="max-w-4xl mx-auto px-4 sm:px-6 lg:px-8 py-12">
        <!-- Problem Description -->
        <div class="bg-white rounded-xl shadow-md overflow-hidden mb-12 card-hover">
            <div class="p-8">
                <div class="flex items-center mb-6">
                    <div class="flex-shrink-0 bg-indigo-500 rounded-lg p-3">
                        <i class="fas fa-question-circle text-white text-2xl"></i>
                    </div>
                    <div class="ml-4">
                        <h2 class="text-2xl font-bold text-gray-800">题目描述</h2>
                        <p class="text-gray-600">给定两个长度相等的整数数组，请重新排列每个数组中的元素，使得对应位置元素相乘的和最小。</p>
                    </div>
                </div>
                <p class="drop-cap text-gray-700 leading-relaxed">
                    这是一个经典的贪心算法问题，考察如何通过合理的排序策略来优化乘积和。问题的关键在于理解如何通过一对数组元素的排序组合，使得它们的点积最小。这与物理中的力矩平衡或经济学中的资源分配有相似之处。
                </p>
            </div>
        </div>

        <!-- Algorithm Explanation -->
        <div class="grid md:grid-cols-2 gap-8 mb-12">
            <!-- Core Idea -->
            <div class="bg-white rounded-xl shadow-md overflow-hidden card-hover">
                <div class="p-8">
                    <div class="flex items-center mb-6">
                        <div class="flex-shrink-0 bg-purple-500 rounded-lg p-3">
                            <i class="fas fa-lightbulb text-white text-2xl"></i>
                        </div>
                        <div class="ml-4">
                            <h2 class="text-2xl font-bold text-gray-800">核心思路</h2>
                            <p class="text-gray-600">贪心算法的精妙应用</p>
                        </div>
                    </div>
                    <div class="prose max-w-none text-gray-700">
                        <p>要最小化两个数组的乘积和，我们需要让大的数与小的数相乘。具体策略是：</p>
                        <ol class="list-decimal pl-6">
                            <li>将一个数组升序排列</li>
                            <li>另一个数组降序排列</li>
                            <li>对应位置元素相乘后求和</li>
                        </ol>
                        <p>这种策略利用了数学中的排序不等式，确保不会出现大数与大数相乘的情况，从而最小化总和。</p>
                    </div>
                </div>
            </div>

            <!-- Complexity Analysis -->
            <div class="bg-white rounded-xl shadow-md overflow-hidden card-hover">
                <div class="p-8">
                    <div class="flex items-center mb-6">
                        <div class="flex-shrink-0 bg-blue-500 rounded-lg p-3">
                            <i class="fas fa-stopwatch text-white text-2xl"></i>
                        </div>
                        <div class="ml-4">
                            <h2 class="text-2xl font-bold text-gray-800">复杂度分析</h2>
                            <p class="text-gray-600">算法效率的量化评估</p>
                        </div>
                    </div>
                    <div class="prose max-w-none text-gray-700">
                        <div class="flex items-start mb-4">
                            <i class="fas fa-clock text-blue-500 mt-1 mr-2"></i>
                            <div>
                                <h3 class="font-semibold">时间复杂度</h3>
                                <p>O(n log n) - 主要由排序操作决定</p>
                            </div>
                        </div>
                        <div class="flex items-start">
                            <i class="fas fa-memory text-blue-500 mt-1 mr-2"></i>
                            <div>
                                <h3 class="font-semibold">空间复杂度</h3>
                                <p>O(1) 或 O(n) - 取决于是否使用原地排序</p>
                            </div>
                        </div>
                    </div>
                </div>
            </div>
        </div>

        <!-- Code Example -->
        <div class="bg-white rounded-xl shadow-md overflow-hidden mb-12 card-hover">
            <div class="p-8">
                <div class="flex items-center mb-6">
                    <div class="flex-shrink-0 bg-green-500 rounded-lg p-3">
                        <i class="fas fa-code text-white text-2xl"></i>
                    </div>
                    <div class="ml-4">
                        <h2 class="text-2xl font-bold text-gray-800">示例代码</h2>
                        <p class="text-gray-600">TypeScript实现</p>
                    </div>
                </div>
                <div class="code-block rounded-lg p-6 mb-6">
                    <pre class="text-gray-200 overflow-x-auto"><code class="language-typescript">
function minProductSum(nums1: number[], nums2: number[]): number {
  nums1.sort((a, b) => a - b);    // 升序排列
  nums2.sort((a, b) => b - a);    // 降序排列
  
  let sum = 0;
  for (let i = 0; i < nums1.length; i++) {
    sum += nums1[i] * nums2[i];   // 对应位置相乘并求和
  }
  return sum;
}
                    </code></pre>
                </div>
                <div class="grid md:grid-cols-3 gap-6">
                    <div class="bg-indigo-50 p-4 rounded-lg">
                        <div class="flex items-center">
                            <i class="fas fa-sort-amount-up-alt text-indigo-500 mr-2"></i>
                            <h3 class="font-semibold">排序策略</h3>
                        </div>
                        <p class="text-sm text-gray-600 mt-2">一个升序一个降序，确保大数乘小数</p>
                    </div>
                    <div class="bg-green-50 p-4 rounded-lg">
                        <div class="flex items-center">
                            <i class="fas fa-plus-circle text-green-500 mr-2"></i>
                            <h3 class="font-semibold">累加求和</h3>
                        </div>
                        <p class="text-sm text-gray-600 mt-2">遍历数组计算对应位置的乘积和</p>
                    </div>
                    <div class="bg-purple-50 p-4 rounded-lg">
                        <div class="flex items-center">
                            <i class="fas fa-project-diagram text-purple-500 mr-2"></i>
                            <h3 class="font-semibold">贪心特性</h3>
                        </div>
                        <p class="text-sm text-gray-600 mt-2">局部最优导致全局最优</p>
                    </div>
                </div>
            </div>
        </div>

        <!-- Visualization -->
        <div class="bg-white rounded-xl shadow-md overflow-hidden mb-12 card-hover">
            <div class="p-8">
                <div class="flex items-center mb-6">
                    <div class="flex-shrink-0 bg-yellow-500 rounded-lg p-3">
                        <i class="fas fa-chart-bar text-white text-2xl"></i>
                    </div>
                    <div class="ml-4">
                        <h2 class="text-2xl font-bold text-gray-800">算法可视化</h2>
                        <p class="text-gray-600">直观理解排序策略的效果</p>
                    </div>
                </div>
                <div class="prose max-w-none">
                    <div class="mermaid">
                        graph LR
                            A[数组A升序] --> B[3, 5, 7, 9]
                            C[数组B降序] --> D[8, 6, 4, 2]
                            B --> E[3×8 + 5×6 + 7×4 + 9×2 = 24+30+28+18 = 100]
                            D --> E
                            F[最小乘积和] --> E
                    </div>
                    <p class="text-gray-600 mt-4 text-center">图：通过排序策略实现最小乘积和的示例 (3×8 + 5×6 + 7×4 + 9×2 = 100)</p>
                </div>
            </div>
        </div>

        <!-- Mathematical Proof -->
        <div class="bg-white rounded-xl shadow-md overflow-hidden card-hover">
            <div class="p-8">
                <div class="flex items-center mb-6">
                    <div class="flex-shrink-0 bg-red-500 rounded-lg p-3">
                        <i class="fas fa-square-root-alt text-white text-2xl"></i>
                    </div>
                    <div class="ml-4">
                        <h2 class="text-2xl font-bold text-gray-800">数学证明</h2>
                        <p class="text-gray-600">为什么这种排序策略有效？</p>
                    </div>
                </div>
                <div class="prose max-w-none text-gray-700">
                    <p>这个问题可以通过数学中的<strong>排序不等式</strong>来解释：</p>
                    <p class="font-serif italic bg-gray-50 p-4 rounded-lg border-l-4 border-red-500">
                        对于两组非负数序列 x₁ ≤ x₂ ≤ ... ≤ xₙ 和 y₁ ≤ y₂ ≤ ... ≤ yₙ，
                        它们的乘积和 x₁y₁ + x₂y₂ + ... + xₙyₙ 是最大的，
                        而 x₁yₙ + x₂yₙ₋₁ + ... + xₙy₁ 是最小的。
                    </p>
                    <p>因此，要让乘积和最小，我们需要将一个数组升序排列，另一个降序排列，然后对应相乘。</p>
                </div>
            </div>
        </div>
    </div>

    <script>
        mermaid.initialize({
            startOnLoad: true,
            theme: 'default',
            flowchart: {
                useMaxWidth: true,
                htmlLabels: true,
                curve: 'basis'
            }
        });
    </script>
</body>
</html>